This paper presents an iterated local search for the fixed-chargeuncapacitated network design problem with user-optimal flow (FCNDP-UOF), whichconcerns routing multiple commodities from its origin to its destination bysigning a network through selecting arcs, with an objective of minimizing thesum of the fixed costs of the selected arcs plus the sum of variable costsassociated to the flows on each arc. Besides that, since the FCNDP-UOF is abi-level problem, each commodity has to be transported through a shortest path,concerning the edges length, in the built network. The proposed algorithmgenerate a initial solution using a variable fixing heuristic. Then a localbranching strategy is applied to improve the quality of the solution. At last,an efficient perturbation strategy is presented to perform cycle-based moves toexplore different parts of the solution space. Computational experiments showsthat the proposed solution method consistently produces high-quality solutionsin reasonable computational times.
展开▼
